package com.kevinkk.array;

/**
 * 在排序数组中查找元素的第一个和最后一个位置
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * 基本参照二分查找的思路
 * 需要注意的是，在第二次查找数组边界时，注意while循环的判断条件
 */

public class FindFirstandLastPositionofElementInSortedArray {
    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int mid = -1;
        while(left <= right){
            mid = (left + right) / 2;
            if(nums[mid] == target){
                break;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        if(left > right) return new int[]{-1, -1};  // 采用静态初始化的方式初始化数组
        int index1 = mid, index2 = mid;
        while(index1 >= 0 && nums[index1] == target) index1--;          // 遍历数组时判断指针边界
        while(index2 < nums.length && nums[index2] == target) index2++; // 遍历数组时判断指针边界
        return new int[]{++index1, --index2};
    }
}
